package leetcodev1.数组;

import java.util.ArrayList;
import java.util.List;

public class LeetCode57 {

    //首先找到新插入元素在有序区间的位置 startIndex和endIndex
    //然后进行合并
    //可不可以在遍历过程中进行合并
    //和官方解差不多
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> merged = new ArrayList<int[]>();
        boolean isAddNewInterval = false;
        for (int[] interval : intervals) {
            int startIndex = interval[0];
            int endIndex = interval[1];

            //直接插入情况
            if (endIndex < newInterval[0]) {
                merged.add(interval);
            } else if (newInterval[1] < startIndex) {
                //直接插入情况
                if (!isAddNewInterval) {
                    merged.add(newInterval);
                    isAddNewInterval = true;
                }
                merged.add(interval);
            } else {
                //其他情况进行区间合并
                newInterval = new int[]{Math.min(newInterval[0], startIndex), Math.max(newInterval[1], endIndex)};
            }
        }

        if (!isAddNewInterval) {
            merged.add(newInterval);
        }

        return merged.toArray(new int[merged.size()][]);
    }
}
